//Author: Joshua Liben
//Compile: g++ -Wall -o PolynomialLinkedList PolynomialLinkedList.cc 
//Toggle '#define TEST' for main method tests.

#include <iostream>
#include <math.h>
#include "PolynomialLinkedList.h"
#define TEST true
using namespace std;

//Evaluates the TermElement value using the variable x
double evaluate(TermElement* input, double x) {
    return input->coeff * pow(x,input->degree);
}

//Checks if a certain degree matches any degree in the polynomial.
//Outputs the relevant term.
TermElement* degreeMatch(TermElement* check, int degree) {
    TermElement* tmp;
    TermElement* prevtmp = check;
    tmp = check;
    while (tmp != NULL) {
        if (tmp->degree == degree) {
            return tmp;
        } else if (tmp->degree < degree) {
            prevtmp = tmp;
            tmp = tmp->next;
        } else if (tmp->next != NULL) {
            if ((tmp->degree > degree) && (tmp->next->degree < degree)) {
                return prevtmp;
            } else { 
                prevtmp = tmp;
                tmp = tmp->next;
            }
        } else {
            return tmp;
        }
    }
    return prevtmp;
}

//Removes any term in a polynomial with coefficient 0
int removeTerm(TermElement* root) {
    TermElement* tmp;
    TermElement* toBeRemoved;
    tmp = root;
    while (tmp->next != NULL) {
        if (tmp->next->coeff == 0) {
            toBeRemoved = tmp->next;
            tmp->next = tmp->next->next;
            delete toBeRemoved;
        }
        if (tmp->next == NULL) {
            return 0;
        } else {
            tmp = tmp->next;
        }
    }
    return 0;
}

//Adds a TermElement to a Polynomial
TermElement* addTerm(TermElement* root, double coefficient, int degree){
    TermElement* relevantTerm = degreeMatch(root, degree);
    if (root == NULL) {
        TermElement* newT = new TermElement();
        newT->degree = degree;
        newT->coeff = coefficient;
        newT->next = NULL;
        return newT;
    } else if(relevantTerm->degree == degree) {
        relevantTerm->coeff += coefficient;
        if (relevantTerm->coeff == 0) {
            removeTerm(root);
        }
        return root;
    } else {
        TermElement* newT = new TermElement();
        if (relevantTerm->degree > degree) {
            TermElement* nextT = relevantTerm->next;
            relevantTerm->next = newT;
            newT->degree = degree;
            newT->coeff = coefficient;
            newT->next = nextT;
            return root;
        } else {
            newT->degree = degree;
            newT->coeff = coefficient;
            newT->next = relevantTerm;
            return newT;
        }
    }
}

//Prints the polynomial
int printPolynomial(TermElement* root) {
    TermElement* origRoot = root;
    TermElement* prevRoot = NULL;
    if (root == NULL) {
        cout << "This Polynomial is Empty.";
    }
    while(root != NULL) {
        if (root->coeff < 0)
           ((root->coeff == -1) && (prevRoot == NULL)) ? cout << " -" : cout << " - ";
       long int coeff = abs((long int)root->coeff);
       (coeff == 1) ?
       cout << "x^(" << root->degree << ")" :
       cout << coeff << "x^(" << root->degree << ")";
       prevRoot = root;
       if (((root = root->next) != NULL) && (root->coeff > 0)) {
        cout << " + ";
    }
}
cout << "\n";
root = origRoot;
return 0;
}

double evaluatePolynomial(TermElement* root, double x) {
    TermElement* origRoot = root;
    double value;
    while (root != NULL) {
        value += evaluate(root, x);
        root = root->next;
    }
    root = origRoot;
    return value;
}

TermElement* derivative(TermElement* root) {
    TermElement* origRoot = root;
    TermElement* newRoot = NULL;
    while (root != NULL) {
        newRoot = addTerm(newRoot, (root->degree * root->coeff), (root->degree - 1));
        root = root->next;
    }
    root = origRoot;
    removeTerm(newRoot); //coefficients of 0 are removed.
    return newRoot;
}

//Remove every element in the list
void freeList(TermElement* root) {
    TermElement* temp = root->next;
    while(temp != NULL) {
        root->next = temp->next;
        temp->next = NULL;
        delete temp;
        temp = root->next;
    }
    delete root;
}

int main () {
    if (TEST) {
        TermElement* ex1 = new TermElement();
        ex1->degree = 2;
        ex1->coeff = 3.0;
        ex1->next = NULL;
        cout << "test1: " << evaluate(ex1, 2.0) << "\n";
        TermElement* ex2 = addTerm(NULL,-1,2);
        ex2 = addTerm(ex2,7,8);
        ex2 = addTerm(ex2,4,5);
        ex2 = addTerm(ex2,3,0);
        cout << "Test2: ";
        printPolynomial(ex1);
        cout << "       ";
        printPolynomial(ex2);
        TermElement* ex3;
        ex3 = derivative(ex2);
        cout << "Test2b: ";
        printPolynomial(ex3);
        cout << "test3: " << evaluatePolynomial(ex2, 2) << "\n";
        freeList(ex1);
        freeList(ex2);
        freeList(ex3);
    }
    return 0;
}
